package alo.p7.work;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @ClassName MaxSlidingWindow
 * @Description 滑动窗口的最大值
 * @Author Fanxc
 * @DATE 2021/3/10 19:46
 * @Version 1.0
 */
public class MaxSlidingWindow {
    void maxSlidingWindow(int[] A,int n,int w,int[] B){
        Deque<Integer> deque=new LinkedList<>();
        //初始化第一个窗口
        for (int i = 0; i < w; i++) {
            while (!deque.isEmpty()&&A[i]>=A[deque.peekLast()]){
                deque.removeFirst();
            }
            deque.addFirst(i);
        }
        for (int i = w; i < n; i++) {
            B[i-w]=A[deque.peekFirst()];//第一个元素
            //如果当前遍历到的数大于双端队列的末尾值（候选窗口最大值），
            //就去除掉队列的末尾值。
            while (!deque.isEmpty()&&A[i]>A[deque.peekLast()]){
                deque.removeFirst();
            }
            //若当前滑动窗口已滑出，则去掉队列首端的最大值（避免最大的一直在队首）
            while (!deque.isEmpty()&&deque.peekFirst()<=i-w){
                deque.removeLast();
            }
            deque.addFirst(i);
        }
        //最后一个元素
        B[n-w]=A[deque.peekFirst()];
    }
}
